package edu.bupt.e1btree;

import java.util.LinkedList;
import java.util.List;

public class T48LCAofBinaryTree {

    private TreeNode resNode;


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return resNode;
    }

    private int dfs(TreeNode root,TreeNode p, TreeNode q){
        // 终止条件
        if(null == root){
            return 0;
        }
        // 收敛条件- 依赖于子树的返回值
        int cur = 0;
        if (root==p || root==q){
            cur = 1;
        }
        int resLeft = dfs(root.left, p, q);
        if (resLeft==2)return 2;
        int resRight = dfs(root.right, p, q);

        int res = cur + resLeft + resRight;
        // 收敛条件
        if ((2==res)&& resLeft<2 && resRight<2){
            resNode = root;
        }

        return res;

    }
}
